public class FirstMissingPositive {
    // 确实的第一个正数
    // https://leetcode.cn/problems/first-missing-positive/?envType=study-plan-v2&envId=top-100-liked
    public int firstMissingPositive(int[] nums) {
        // 可能的结果是在[1,n]之间的，所以我们先遍历一遍数组，将[1,n]之外的元素都替换成不影响结果的值
        // 然后再遍历一遍数组，看看哪些元素是存在的，存在的话就将nums[nums[i]]替换成负数
        int len = nums.length;
        for (int i = 0; i < len; i++) {
            if (nums[i] <= 0 || nums[i] > len) {
                nums[i] = len + 1;
            }
        }
        for (int i = 0; i < len; i++) {
            int n = Math.abs(nums[i]);
            if (n <= len) {
                nums[n-1] = -Math.abs(nums[n-1]);
            }
        }
        for (int i = 0; i < len; i++) {
            if (nums[i] > 0) {
                return i + 1;
            }
        }
        return len+1;
    }
}
